МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ національний університет “Львівська політехніка”
Лабораторна робота № 5 "Розробка та дослідження ефективності методів сортування" № варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1= =( 8 + 115)%30 + 1 =123%30 + 1= 3+1=4 Львів – 2012 1. МЕТА РОБОТИ Вивчення, реалізація та дослідження ефективності методів сортування даних. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування. Провести дослідження побудованого методу за такою схемою: 1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний). 2). Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування. 3). Дослідити метод cортування на стійкість. 4). Дослідити метод cортування на економність використання пам’яті. 5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.). 6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому (
) і в найгіршому (
) випадках. Середні значення кількості порівнянь (
) і кількості перестановок (
) визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей. Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу. № варіанта 4. Сортування методом підрахунку порівнянь [1, 94-97 c.] 3. Опис алгоритму сортування Сортування шляхом пiдрахунку. Кожен елемент порiвнюється з усiма iншими; кiнцевце положення елемента визначається пiсля пiдрахунку числа меньших ключiв. Цей простий метод заснований на тому, що j-й ключ в кiнцевiй впорядкованiй послiдовностi перевищуєрiвно ] —1 решти ключiв.По-iншому, якщо вiдомо, що деякий ключ перевищуєрiвно 27 iнших i якщо нiякi два ключа не рiвнi, то пiсля cортування вiдповiдний запис має зайняти 28-е мiсце. Таким чином, iдея полягає в тому, щоб порiвняти попарно всi ключi i пiдрахувати, скiльки з них менше кожного окремого ключа. Очевидний спосiб виконання поставленної задачi такий: ((порiвняти Кi с Кj) при 1 < j < N) при I < i < N; Бiльше половини цих операцiй зайвi, оскiльки не треба порiвнювати ключ сам з собою i пiсля порiвняння Кa з Кb вже не треба порiвнювати Кb з Кa.Тому достатньо ((порiвняти Кi с Кj) при 1 <= j< i) при 1 < i<= N. Дiстаємо наступний алгоритм. Алгоритм .Цей алгоритм сортує записи R1,...,Rn по ключах К1,..., .Кn, використовуючи допомiжну таблицю COUNT[1], ..., COUNT[N] для пiдрахунку числа ключiв, меньших вiд данного.Пiсля завершення алгоритму величина COUNT[j] -1 визначає кiнцеве положення запису Rj. С1. [скинути лiчильники СОUNT.] Встановити в лiчильниках COUNT[1] - СОUNT [N] нулi. С2. [Цикл по i.] виконати крок СЗ при j = N, N—1, ..., 2 потiм завершує виконання процедури. СЗ. [Цикл по j.] виконати крок С4 при j = i-1, i-2, ..., 1. С4. [порiвняти Кi : Kj.] якщо Кi < Кj, то збiльшити СOUNT[j] на 1; в протилежному випадку збiльшити COUNT[i] на 1. В данному алгоритмi записи не перемiщуються, оскiльки таблиця СOUNT визначає кiнцеве положення записiв - вказує, куди треба переслати запис Rj, а не запис, який треба пересл...